A public key certificate (hereinafter “certificate”) authenticates a public key used in a secure encrypted transaction that utilizes a public key and private key pair. Prior to engaging in a secure transaction that uses the public key, it is important to ensure that the certificate authority that issued the certificate has not revoked the certificate. To facilitate this determination, certificate authorities periodically issue certificate revocation lists (CRLs) that identify revoked certificates.
A CRL is a data structure that includes a CRL entry for each revoked certificate. A CRL also contains a digital signature that can be used to authenticate the CRL. A CRL is encoded in accordance with a particular format such as Abstract Syntax Notation One (ASN.1). A CRL may contain thousands or even millions of CRL entries. Typically a CRL is processed by reading the CRL and building an in-memory data structure that includes each CRL entry. Once built, the in-memory data structure can be rapidly searched to determine whether a certificate has been revoked. However, the generation of the in-memory structure may utilize relatively large amounts of memory, reducing the memory available to other processes, and decoding thousands or millions of CRL entries may take a relatively long period of time, resulting in unacceptable processing delays.
Modifying a CRL by a certificate authority may be equally or even more time-consuming than reading the CRL, since any change to the CRL requires that the entire CRL be processed by a signature algorithm to generate the digital signature that is used to authenticate the CRL.